package main

import (
	"errors"
)

import . "local/algorithm/util"

/*
*
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

链接：https://leetcode-cn.com/problems/add-two-numbers-ii

此题与"2.两数之和"十分相似
要点

	1.对数值加法计算要从低位向高位进位计算，这里借助两个栈来实现"先进后出"
	2.计算时从低位向高位计算，最后返回链表要采用头插入方式，将高位放于最前列
*/
func main() {
	l1 := GenerateLinkedList([]int{1, 2, 3})
	l2 := GenerateLinkedList([]int{4, 5, 6})
	list := addTwoNumbers(l1, l2)
	PrintLinkedList(list)
}

type Stack struct {
	data []int
}

func (s *Stack) Pop() int {
	tmp := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return tmp
}

func (s *Stack) Push(e int) bool {
	s.data = append(s.data, e)
	return true
}

func (s *Stack) Peek() (int, error) {
	if s.Empty() {
		return 0, errors.New("empty stack")
	} else {
		return s.data[len(s.data)-1], nil
	}
}

func (s *Stack) Empty() bool {
	if len(s.data) == 0 {
		return true
	} else {
		return false
	}
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}

	s1, s2 := &Stack{}, &Stack{}
	for l1 != nil {
		s1.Push(l1.Val)
		l1 = l1.Next
	}
	for l2 != nil {
		s2.Push(l2.Val)
		l2 = l2.Next
	}

	carry := 0
	dummyNode := &ListNode{}
	//current := dummyNode
	for carry != 0 || (!s1.Empty()) || (!s2.Empty()) {
		sum := carry
		if !s1.Empty() {
			sum += s1.Pop()
		}

		if !s2.Empty() {
			sum += s2.Pop()
		}

		//头插法插入链表
		tmp := &ListNode{Val: sum % 10, Next: nil}
		tmp.Next = dummyNode.Next
		dummyNode.Next = tmp
		//current.Forward = &ListNode{Val: sum % 10, Forward: nil}
		//current = current.Forward
		carry = sum / 10
	}

	return dummyNode.Next
}
